#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/15 16:40
# ===========================================
#       题目名称： 6. N 字形变换
#       题目地址： https://leetcode.cn/problems/zigzag-conversion/
#       题目描述： https://note.youdao.com/s/aSyZ5Ulm
# ===========================================


class Solution:
    def convert(self, s, numRows):
        if len(s) == 1 or numRows == 1:
            return s
        dp = [["" for _ in range(len(s))] for _ in range(numRows)]  # 定义迷宫
        stack = list(s)  # 定义栈
        x, y = 0, 0  # 定义两个指针
        up, down = True, False  # 往上走 往下走
        is_change = True
        while stack:
            if is_change:
                # print(x, y)
                element = stack.pop(0)
                dp[x][y] = element
                is_change = False
            """
                0       4
                1   3   5
                2       6
                
                00      02      04
                10  11  12  13  14
                20      22      24
            """
            if up:  # 往上走
                if x + 1 > numRows - 1:
                    up = False
                    down = True
                else:
                    x += 1
                    is_change = True
            if down:  # 往下走
                if x - 1 < 0:
                    down = False
                    up = True
                else:
                    x -= 1
                    y += 1
                    is_change = True
        return "".join(["".join(item) for item in dp])


if __name__ == '__main__':
    s = Solution()
    # "PAHNAPLSIIGYIR"
    print(s.convert(s="PAYPALISHIRING", numRows=3))
    # "PINALSIGYAHRPI"
    print(s.convert(s="PAYPALISHIRING", numRows=4))
    # "A"
    print(s.convert(s="A", numRows=1))
    # "AB"
    print(s.convert(s="AB", numRows=1))